Certain cryptographic systems implementing methods such as for example the digital signing of a message or its encryption, require the generation of cryptographic key pairs. The public key is shared as plaintext by the cryptographic system with the addressee systems receiving the processed message whereas the private key is kept secret.
Generation of public and private key pairs being a sensitive operation, test mechanisms are usually provided for verifying their integrity.
For example, the American FIPS standard 140-2 published by the NIST (the initials standing for “National Institute of Standards and Technology”) provides for such a test (entitled “pair-wise consistency test”).
In the case of cryptographic methods of RSA type (the initials standing for “Rivest Shamir Adelman”), the key pair is obtained in the following manner.
To obtain p and q, two large prime numbers, the following two steps are repeated:                obtaining of two candidate numbers p and q on the basis of numbers drawn at random in the set Zn of the additive group of integers modulo n, and        testing of the primality of the p and q candidates (for example according to a probabilistic primality test, for example of Miller-Rabin type, for example in accordance with FIPS standard 140-2,until a prime number is obtained.        
The product of the numbers p and q thus forms a number n (n=p·q).
Thereafter, the number Φ(n)=(p−1)·(q−1) is computed (Φ being the Euler indicator function, or “totient” as it is termed).
The public key is thereafter formed by the numbers n and e, with e, “the public exponent”, being an integer such that:                1<e<Φ(n), and        e and Φ (n) are mutually prime (gcd(e, Φ(n))=1, “gcd” being the initials standing for “greatest common divisor”).        
The private key, on the other hand, is formed by the numbers n and d, with d, “the private exponent”, being an integer such that:                d·e=1 mod λ(n), with        λ(n) being the least common multiple between p−1 and q−1 (λ(n)=lcm(p−1, q−1), “lcm” being the initials standing for “least common multiplier”).        
When the cryptographic method is an encryption of a message m (m belonging to Zn), the integrity test provided for by FIPS standard 140-2 can be summarized as follows:                1) the message m is encrypted with the public key so as to obtain an encrypted message c=me mod n,        2) the encrypted message c is decrypted with the private key so as to obtain a decrypted message m′=cd mod n, and        3) it is verified that the initial message m and the decrypted message are the same (m′=m).        
When the cryptographic method is a signing of a message m (m belonging to Zn), the integrity test provided for by FIPS standard 140-2 can be summarized as follows:                1) the message m is signed with the private key so as to obtain a signature s=(m)d mod n, (or optionally s=(H(m))d, H being a hash function,        2) a value h′ is computed as h′=se mod n, and        3) it is verified that the value h′ thus computed and the message m are the same (or optionally that the value h′ and the digest of the message under the hash function are the same (h′=H(m)).        